package algorithmForInterview40;

/**
 * @author 03010570
 * @date 2020/06/18
 * describe:    206、反转链表    https://leetcode-cn.com/problems/reverse-linked-list/
 */
public class LeetCode_206 {
    public static void main(String[] args) {
        LeetCode_206 code206 = new LeetCode_206();
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        ListNode list = code206.reverseList2(node);
        while (list != null) {
            System.out.print(list.val + " -> ");
            list = list.next;
        }
    }

    /**
     *  思路： 迭代
     *      1、 两个变量， 当前节点 和 上一个节点
     *       pre = null ;
     *       curr = head ;
     *      2、赋值： 当前节点的 next 指向上一个节点，上一个节点 等于 当前节点，当前节点 =  当前节点的下一个节点。
     *       nextNode = curr.next ;
     *       curr.nect = pre ;
     *       pre = curr ;
     *       curr = nextNode;
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = nextTemp;
        }
        return pre;
    }


    /**
     *  2、递归
     *      1、以 4 -> 5 为 例， recerseList(4) 4.next(5).next = 5 ; 得出 4->5->4,
     *          4.next = null 切断 4->5 的连接 ；5->4
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        if(head==null || head.next==null){
            return  head;
        }
        ListNode result = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return  result;
    }


}
